package com.demo.study.algorithm.sorts;

import static com.demo.study.utils.ArrayUtil.intRandomArray;
import static com.demo.study.utils.ArrayUtil.printArray;

/**
 * 希尔排序
 * 希尔排序是对插入排序的一个改进版：根据间隙分组之后，再进行插入排序，直到间隙为1，就完成了
 *
 * @author Baymax
 * @since 2024-08-15
 */
public class B05_ShellSort {
    public static void main(String[] args) {
        int[] nums = intRandomArray();
        printArray(nums);
        shellSort(nums);
        printArray(nums);
    }

    /**
     * 希尔排序
     */
    public static void shellSort(int[] nums) {
        // gap 即为间隔，每次长度除以2即可
        // 在插入排序的实现上，low = 1，把1替换为gap即可
        for (int gap = nums.length >> 1; gap >= 1; gap = gap >> 1) {
            for (int low = gap; low < nums.length; low++) {
                int t = nums[low];
                int i = low - gap;
                while (i >= 0 && nums[i] > t) {
                    nums[i + gap] = nums[i]; // 将 nums[i] 向右移动一位
                    i-= gap;
                }
                if (i != low - gap) {
                    nums[i + gap] = t; // 将 t 赋值到正确位置
                }
            }
        }

    }
}
